home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource5 / 347_01 / tavl_del.c < prev    next >
C/C++ Source or Header  |  1991-10-19  |  8KB  |  247 lines
  1. /*:file:version:date: "%n    V.%v;  %f"
  2.  * "TAVL_DEL.C    V.11;  19-Oct-91,14:47:10"
  3.  *
  4.  *      Module:     tavl_delete
  5.  *      Purpose:    Delete from TAVL tree the node whose identifier
  6.  *                  equals "*identifier", if such a node exists. Returns
  7.  *                  non-zero if & only if a node is deleted.
  8.  *
  9.  * !!NOTE!!     Programs that use this module must also link in the module
  10.  *              whose source is in the file "TAVLREBL.C".
  11.  *
  12.  *  Released to the PUBLIC DOMAIN
  13.  *
  14.  *               author:    Bert C. Hughes
  15.  *                          200 N.Saratoga
  16.  *                          St.Paul, MN 55104
  17.  *                          Compuserve 71211,577
  18.  */
  19.  
  20.    /* Debugging "assert"s are in the code to test integrity of the    */
  21.    /* tree. All assertions should be removed from production versions */
  22.    /* of the library by compiling the library with NDEBUG defined.    */
  23.    /* See the header "assert.h".*/
  24.  
  25. #include <assert.h>
  26. #include "tavltree.h"
  27. #include "tavlpriv.h"
  28.  
  29. static TAVL_nodeptr remove_node(TAVL_treeptr tree, TAVL_nodeptr p, char *deltaht);
  30. static TAVL_nodeptr remove_max(TAVL_nodeptr p, TAVL_nodeptr *maxnode, char *deltaht);
  31. static TAVL_nodeptr remove_min(TAVL_nodeptr p, TAVL_nodeptr *minnode, char *deltaht);
  32.  
  33. /*  Development note:  the routines "remove_min" and "remove_max" are
  34.     true recursive routines; i.e., they make calls to themselves. The
  35.     routine "tavl_delete" simulates recursion using a stack (a very deep
  36.     one that should handle any imaginable tree size - up to approximately
  37.     1 million squared nodes).  I arrived at this particular mix by using
  38.     Borland's Turbo Profiler and a list of 60K words as a test file to
  39.     example1.c, which should be included in the distribution package.
  40.     -BCH
  41. */
  42.  
  43.  
  44. int tavl_delete (TAVL_treeptr tree, void *key)
  45. {
  46.     char rb, deltaht;
  47.     int side;
  48.     int  found = deltaht = 0;
  49.     register TAVL_nodeptr p = Leftchild(tree->head);
  50.     register int cmpval = -1;
  51.     register TAVL_nodeptr q;
  52.  
  53.     struct stk_item {
  54.             int side;
  55.             TAVL_nodeptr p;
  56.         } block[RECUR_STACK_SIZE];
  57.  
  58.     struct stk_item *next = block;   /* initialize recursion stack */
  59.  
  60. #define PUSH_PATH(x,y)  (next->p = (x),  (next++)->side = (y))
  61. #define POP_PATH(x)     (x = (--next)->side, (next->p))
  62.  
  63.     tree->head->bf = 0;      /* prevent tree->head from being rebalanced */
  64.  
  65.     PUSH_PATH(tree->head,LEFT);
  66.  
  67.     while (p) {
  68.         cmpval = (*tree->cmp)(key,(*tree->key_of)(p->dataptr));
  69.         if (cmpval > 0) {
  70.             PUSH_PATH(p,RIGHT);
  71.             p = Rightchild(p);
  72.         }
  73.         else if (cmpval < 0) {
  74.             PUSH_PATH(p,LEFT);
  75.             p = Leftchild(p);
  76.         }
  77.         else /* cmpval == 0 */ {
  78.             q = p;
  79.             p = NULL;
  80.             found = 1;
  81.         }
  82.     } /* end while(p) */
  83.  
  84.     if (!found) return 0;
  85.  
  86.     (*tree->free_item)(q->dataptr);
  87.     q = remove_node(tree,q,&deltaht);
  88.  
  89.     do {
  90.         p = POP_PATH(side);
  91.  
  92.         if (side != RIGHT)
  93.             p->Lptr = q;
  94.         else
  95.             p->Rptr = q;
  96.  
  97.         q = p;  rb = 0;
  98.  
  99.         if (deltaht) {
  100.             p->bf -= side;
  101.             switch (p->bf) {
  102.                 case 0:     break;  /* longest side shrank to equal shortest */
  103.                                     /* therefor deltaht remains true */
  104.                 case LEFT:
  105.                 case RIGHT: deltaht = 0;/* other side is deeper */
  106.                             break;
  107.  
  108.                 default:    {
  109.                                 q = rebalance_tavl(p,&deltaht);
  110.                                 rb = 1;
  111.                             }
  112.             }
  113.         }
  114.     } while ((p != tree->head) && (rb || deltaht));
  115.  
  116.     return 1;
  117.  
  118. #undef PUSH_PATH
  119. #undef POP_PATH
  120.  
  121. } /* tavl_delete */
  122.  
  123.  
  124. static TAVL_nodeptr remove_node(TAVL_treeptr tree, TAVL_nodeptr p, char *deltaht)
  125. {
  126.     char dh;
  127.     TAVL_nodeptr q;
  128.  
  129.     *deltaht = 0;
  130.  
  131.     if (p->bf != LEFT) {
  132.         if (RLINK(p)) {
  133.             p->Rptr = remove_min(p->Rptr,&q,&dh);
  134.             if (dh) {
  135.                 p->bf += LEFT;  /* becomes 0 or LEFT */
  136.                 *deltaht = (p->bf) ? 0 : 1;
  137.             }
  138.         }
  139.         else { /* leftchild(p),rightchild(p) == NULL */
  140.             assert(p->bf == 0);
  141.             assert(LTHREAD(p));
  142.  
  143.             *deltaht = 1;           /* p will be removed, so height changes */
  144.             if (p->Rptr->Lptr == p) { /* p is leftchild of it's parent */
  145.                 p->Rptr->Lbit = THREAD;
  146.                 q = p->Lptr;
  147.             }
  148.             else {  /* p is rightchild of it's parent */
  149.                 assert(p->Lptr->Rptr == p);
  150.                 p->Lptr->Rbit = THREAD;
  151.                 q = p->Rptr;
  152.             }
  153.             (*tree->dealloc)(p);
  154.             return q;
  155.         }
  156.     }
  157.     else { /* p->bf == LEFT */
  158.         p->Lptr = remove_max((p->Lptr),&q,&dh);
  159.         if (dh) {
  160.             p->bf += RIGHT;      /* becomes 0 or RIGHT */
  161.             *deltaht = (p->bf) ? 0 : 1;
  162.         }
  163.     }
  164.  
  165.     p->dataptr = q->dataptr;
  166.     (*tree->dealloc)(q);
  167.     return p;
  168. }
  169.  
  170. static TAVL_nodeptr remove_min(TAVL_nodeptr p, TAVL_nodeptr *minnode, char *deltaht)
  171. {
  172.     char dh = *deltaht = 0;
  173.  
  174.     if (LLINK(p)) { /* p is not minimum node */
  175.         p->Lptr = remove_min(p->Lptr,minnode,&dh);
  176.         if (dh) {
  177.             p->bf += RIGHT;
  178.             switch (p->bf) {
  179.                 case 0: *deltaht = 1;
  180.                         break;
  181.                 case RIGHT+RIGHT:
  182.                         p = rebalance_tavl(p,deltaht);
  183.             }
  184.         }
  185.         return p;
  186.     }
  187.     else { /* p is minimum */
  188.         *minnode = p;
  189.         *deltaht = 1;
  190.         if (RLINK(p)) {
  191.             assert(p->Rptr->Lptr == p);
  192.             assert(LTHREAD(p->Rptr) && RTHREAD(p->Rptr));
  193.  
  194.             p->Rptr->Lptr = p->Lptr;
  195.             return p->Rptr;
  196.         }
  197.         else
  198.             if (p->Rptr->Lptr != p) {   /* was first call to remove_min, */
  199.                 p->Lptr->Rbit = THREAD; /* from "remove", not remove_min */
  200.                 return p->Rptr;         /* p is never rightchild of head */
  201.             }
  202.             else {
  203.                 p->Rptr->Lbit = THREAD;
  204.                 return p->Lptr;
  205.             }
  206.     }
  207. }
  208.  
  209. static TAVL_nodeptr remove_max(TAVL_nodeptr p, TAVL_nodeptr *maxnode, char *deltaht)
  210. {
  211.     char dh = *deltaht = 0;
  212.  
  213.     if (RLINK(p)) { /* p is not maximum node */
  214.         p->Rptr = remove_max(p->Rptr,maxnode,&dh);
  215.         if (dh) {
  216.             p->bf += LEFT;
  217.             switch (p->bf) {
  218.                 case 0: *deltaht = 1;
  219.                         break;
  220.                 case LEFT+LEFT:
  221.                         p = rebalance_tavl(p,deltaht);
  222.             }
  223.         }
  224.         return p;
  225.     }
  226.     else { /* p is maximum */
  227.         *maxnode = p;
  228.         *deltaht = 1;
  229.         if (LLINK(p)) {
  230.             assert(LTHREAD(p->Lptr) && RTHREAD(p->Lptr));
  231.             assert(p->Lptr->Rptr == p);
  232.  
  233.             p->Lptr->Rptr = p->Rptr;
  234.             return p->Lptr;
  235.         }
  236.         else
  237.             if (p->Rptr->Lptr == p) {   /* p is leftchild of its parent */
  238.                 p->Rptr->Lbit = THREAD; /* test must use p->Rptr->Lptr */
  239.                 return p->Lptr;         /* because p may be predecessor */
  240.             }                           /* of head node */
  241.             else {
  242.                 p->Lptr->Rbit = THREAD;  /* p is rightchild of its parent */
  243.                 return p->Rptr;
  244.             }
  245.     }
  246. }
  247.